public class StepChecker {

	public static void main(String[] args) {
		StepChecker checker = new StepChecker();

		// . . o . .
		// . o . o .
		// . . o . .
		// . . . o .
		// . . o . o
		String[] board = new String[] { "..o..", ".o.o.", "..o..", "...o.",
				"..o.o" };
		System.out.println(checker.getMinStep(board, 3));

	}

	public int getMinStep(String[] board, int k) {
		if (board == null || board.length == 0)
			return -1;

		int width = board[0].length();
		if (width == 0)
			return -1;

		int height = board.length;

		int minStep = Integer.MAX_VALUE;
		for (int x = 0; x < width; ++x)
			for (int y = 0; y < height; ++y)
				for (int w = 1; w <= width - x; ++w)
					for (int h = 1; h <= height - y; ++h)
						if (isFinalState(board, k, x, y, w, h)) {
							int step = subMinStep(x, y, w, h, width, height);
							if (step < minStep)
								minStep = step;
						}

		if (minStep != Integer.MAX_VALUE)
			return minStep;
		else
			return -1;
	}

	public int subMinStep(int x, int y, int w, int h, int width, int height) {
		int cutRight = width - x - w;
		int cutBottom = height - y - h;

		return Math.max(x, cutRight) + 2 * Math.min(x, cutRight)
				+ Math.max(y, cutBottom) + 2 * Math.min(y, cutBottom);
	}

	public boolean isFinalState(String[] board, int k, int x, int y, int w,
			int h) {
		int c = 0;
		for (int i = 0; i < w; ++i)
			for (int j = 0; j < h; ++j) {
				if (board[j + y].charAt(i + x) == 'o')
					c++;
				if (c > k)
					return false;
			}

		return c == k;
	}
}
